#include<bits/stdc++.h>//BAONI
using namespace std;
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

int t,k;
int F[2003][2003];
int A[2003][2003];
int ans;
int n,m;

void init()
{
	F[0][0]=1;
	for(int i=1;i<=2001;++i)
	{
		for(int j=1;j<=i;++j)
		{
			F[i][j]=F[i-1][j]+F[i-1][j-1];
			if(!(F[i][j]%k))A[i][j]=1;
			F[i][j]%=k;
		}
	}
	return ;
}

int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	read(t);read(k);
	init();
	while(t--)
	{
		read(n);read(m);
		ans=0;
		for(int i=2;i<=n+1;++i)
		{
			int z=min(i,m+1);
			for(int j=2;j<=z;++j)
			{
				ans+=A[i][j];
			}
		}
		printf("%d\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
